Building on the comparative table of notations, Postfix (Reverse Polish Notation, or RPN) is the ideal format for stack evaluation because it resolves all ambiguity inherent in standard Infix expressions like A + B * C.
- By defining a fixed order of operations, RPN allows for a linear, single-pass scan of the expression without needing to consult complex external precedence rules or parentheses.
- The entire evaluation process relies strictly on the FILO principle of the stack:
- Operands (Numbers/Variables): Any operand encountered is immediately Pushed onto the stack. They wait in storage.
- Operators (+, -, *, /): When an operator is encountered, it acts as a signal to execute. It must Pop the top two operands, perform the operation, and then Push the single result back onto the stack.
This simplicity means the evaluation complexity is $O(n)$, where $n$ is the number of tokens in the expression.
Postfix Evaluation Rules
| Process Component | Input Token Type | Action on Stack |
|---|---|---|
Operands (e.g., A, B, 2, 3) |
Operand | PUSH onto the stack. |
Operators (e.g., +, -, *) |
Operator | 1. POP the top two elements (op2, then op1).2. Calculate: op1 <operator> op2.3. PUSH the single result. |